From f78e96610ab3ae1421e84bf8203d9c407e010333 Mon Sep 17 00:00:00 2001
From: "Miouyouyou (Myy)" <myy@miouyouyou.fr>
Date: Wed, 15 May 2019 20:07:56 +0200
Subject: [PATCH 1/8] lib: Add sort_r for the Rockchip H264 driver.

I doubt that this will be ported though.

Taken from bbrazillon rk-vpu1-h264 (WIP draft branch)
https://github.com/bbrezillon/linux/commits/rk-vpu1-h264

Patch butchered by myself.

Signed-off-by: Miouyouyou (Myy) <myy@miouyouyou.fr>
---
 include/linux/sort.h |  5 +++++
 lib/sort.c           | 48 +++++++++++++++++++++++++++++++++++++++---------
 2 files changed, 44 insertions(+), 9 deletions(-)

diff --git a/include/linux/sort.h b/include/linux/sort.h
index 2b99a5dd0..c37e0f608 100644
--- a/include/linux/sort.h
+++ b/include/linux/sort.h
@@ -4,6 +4,11 @@
 
 #include <linux/types.h>
 
+void sort_r(void *base, size_t num, size_t size,
+	    int (*cmp)(const void *, const void *, void *),
+	    void (*swap)(void *, void *, int),
+	    void *priv);
+
 void sort(void *base, size_t num, size_t size,
 	  int (*cmp)(const void *, const void *),
 	  void (*swap)(void *, void *, int));
diff --git a/lib/sort.c b/lib/sort.c
index d6b7a202b..51acfc925 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -43,12 +43,13 @@ static void generic_swap(void *a, void *b, int size)
 }
 
 /**
- * sort - sort an array of elements
+ * sort_r - sort an array of elements
  * @base: pointer to data to sort
  * @num: number of elements
  * @size: size of each element
  * @cmp_func: pointer to comparison function
  * @swap_func: pointer to swap function or NULL
+ * @priv: private data passed to the compare function
  *
  * This function does a heapsort on the given array. You may provide a
  * swap_func function optimized to your element type.
@@ -58,10 +59,10 @@ static void generic_swap(void *a, void *b, int size)
  * O(n*n) worst-case behavior and extra memory requirements that make
  * it less suitable for kernel use.
  */
-
-void sort(void *base, size_t num, size_t size,
-	  int (*cmp_func)(const void *, const void *),
-	  void (*swap_func)(void *, void *, int size))
+void sort_r(void *base, size_t num, size_t size,
+	    int (*cmp_func)(const void *, const void *, void *),
+	    void (*swap_func)(void *, void *, int size),
+	    void *priv)
 {
 	/* pre-scale counters for performance */
 	int i = (num/2 - 1) * size, n = num * size, c, r;
@@ -80,9 +81,9 @@ void sort(void *base, size_t num, size_t size,
 		for (r = i; r * 2 + size < n; r  = c) {
 			c = r * 2 + size;
 			if (c < n - size &&
-					cmp_func(base + c, base + c + size) < 0)
+			    cmp_func(base + c, base + c + size, priv) < 0)
 				c += size;
-			if (cmp_func(base + r, base + c) >= 0)
+			if (cmp_func(base + r, base + c, priv) >= 0)
 				break;
 			swap_func(base + r, base + c, size);
 		}
@@ -94,13 +95,42 @@ void sort(void *base, size_t num, size_t size,
 		for (r = 0; r * 2 + size < i; r = c) {
 			c = r * 2 + size;
 			if (c < i - size &&
-					cmp_func(base + c, base + c + size) < 0)
+			    cmp_func(base + c, base + c + size, priv) < 0)
 				c += size;
-			if (cmp_func(base + r, base + c) >= 0)
+			if (cmp_func(base + r, base + c, priv) >= 0)
 				break;
 			swap_func(base + r, base + c, size);
 		}
 	}
 }
+EXPORT_SYMBOL(sort_r);
+
+static int cmp_func_wrapper(const void *a, const void *b, void *priv)
+{
+	int (*cmp_func)(const void *, const void *) = priv;
+	return cmp_func(a, b);
+}
 
+/**
+ * sort - sort an array of elements
+ * @base: pointer to data to sort
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp_func: pointer to comparison function
+ * @swap_func: pointer to swap function or NULL
+ *
+ * This function does a heapsort on the given array. You may provide a
+ * swap_func function optimized to your element type.
+ *
+ * Sorting time is O(n log n) both on average and worst-case. While
+ * qsort is about 20% faster on average, it suffers from exploitable
+ * O(n*n) worst-case behavior and extra memory requirements that make
+ * it less suitable for kernel use.
+ */
+void sort(void *base, size_t num, size_t size,
+	  int (*cmp_func)(const void *, const void *),
+	  void (*swap_func)(void *, void *, int size))
+{
+	return sort_r(base, num, size, cmp_func_wrapper, swap_func, cmp_func);
+}
 EXPORT_SYMBOL(sort);
-- 
2.16.4

